/**********
* 一个简单的基于list的lru缓存淘汰算法
*这是一个带头的链表（如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表）
*
*
*/

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

typedef int data_type;

//定义
typedef struct snode_t {
    data_type data;
    struct snode_t *next;
}snode_t;

typedef struct slist_t {
    int maxsize;
    int length;
    snode_t *head;
}slist_t;

/*SList* SList_init(void)
{
    SList *slist = malloc(SList);
    if (NULL == slist) return NULL;
    slist->head = malloc(SNode);     //申请头节点
    if (NULL == slist->head) return NULL;
    slist->head -> next = NULL;
    slist-> MaxSize = 10;
    slist -> length = 0;

    return slist;
}*/

slist_t *slist_init(int maxsize)
{
    slist_t *slist = malloc(sizeof(slist_t));
    if (NULL == slist) return NULL;
    slist->head = malloc(sizeof(snode_t));     //申请头节点
    if (NULL == slist->head) return NULL;
    slist->head -> next = NULL;
    if (maxsize < 10)
        slist-> maxsize = 10;
    else slist->maxsize = maxsize;
    slist -> length = 0;

    return slist;
}

void slist_free(slist_t * slist)
{
    snode_t * ptr, * temp;
    ptr = slist -> head;

    while(ptr->next != NULL) {
        temp = ptr->next;
        ptr->next = ptr->next->next;
        temp->next = NULL;
        free(temp);
    }
    free(ptr);
    slist -> head = NULL;
    slist -> length = 0;
}

void insert_elem_at_begin(slist_t * slist, data_type x)     //头部插入节点
{
    snode_t *ptr = malloc(sizeof(snode_t));
     if (NULL == ptr) return exit(1);
    ptr->data = x;
    ptr->next = slist->head->next;
    slist->head->next = ptr;

    slist->length ++;
}

bool find_elem(slist_t * slist, data_type x)              //查找x，存在则返回1，不存在则返回0
{
    snode_t * ptr;
    ptr = slist->head;

    while (ptr->next != NULL) {
        if (ptr->next->data == x) return true;
        ptr = ptr->next;
    }
    return false;
}

void delete_elem_at_end(slist_t * slist)             //删除尾节点
{
    snode_t * ptr = NULL;
    snode_t * prev = NULL;    
    ptr = slist->head;

    while (ptr->next != NULL) {
        prev = ptr;
        ptr = ptr->next;
    }

    prev->next = ptr->next;
    free(ptr);
    ptr=NULL;

    slist -> length --;

/*
    while (ptr->next != NULL && ptr->next->next != NULL) 
        ptr = ptr->next;
    
    prev = ptr->next;
    ptr->next = prev->next;
    free(prev);
    prev=NULL;
    slist -> length --;
*/
}

bool delete_elem(slist_t * slist, data_type x)    //删除指定节点，如果存在则删除，返回1，如果不存在，则删除失败返回0
{
    snode_t * ptr, *temp;
    ptr = slist->head;

    while (ptr -> next != NULL) {
        if (ptr->next->data == x) {
            temp = ptr->next;
            ptr->next = ptr->next->next;
            free(temp);
            temp = NULL;
            slist->length--;
            return true;
        }
        ptr = ptr->next;
    }
    return false;
}

bool is_empty(slist_t * slist)                  // 查看链表是否为空，1表示不为空，0表示为空
{
    return (slist->head == NULL || slist-> length == 0) ?  0 : 1;
}
bool is_full(slist_t * slist)                   // 查看链表是否满，1表示不满，0表示满
{
    return (slist-> length == slist->maxsize) ?  0 : 1;
}
void print_all(slist_t *slist)
{
    snode_t *ptr, *temp;
    ptr = slist->head;
    while (ptr->next != NULL) {
        ptr = ptr->next;
        printf("%d    ", ptr-> data);
    }
    printf("\n");
}

//针对此应用的优化，查找,返回指定元素的前一个节点的指针
snode_t * find_elem_optim(slist_t *slist, data_type x)
{
     snode_t *ptr;
     if (slist->head == NULL) return NULL;
     ptr = slist->head;
     while (ptr->next != NULL) {
         if (ptr->next->data == x) return ptr;
         ptr = ptr->next;
     }
     return NULL;
}


// 针对此应用的优化，删除
void  delete_elem_optim (slist_t *slist, snode_t *x)
{
     snode_t *temp;
     temp = x->next;
     x->next = x->next->next;
     slist->length --;
     free(temp);
}

int main(int argc, char **argv)
{
    printf("test\n");
    slist_t *slist = slist_init(10);
    int num = 0;
    while  (1) {
        printf("please enter a number,99999== exit \n");
        scanf("%d", &num);
        if (num == 99999) break;

/*        if (find_elem(slist, num)) {
            delete_elem(slist, num);
            insert_elem_at_begin(slist, num);
        }*/
        snode_t *pre_ptr = find_elem_optim(slist, num);
        if (pre_ptr != NULL) {
            delete_elem_optim(slist, pre_ptr);
            insert_elem_at_begin(slist, num);
        }
        else {
            if (is_full(slist)) insert_elem_at_begin(slist, num);
            else {
                delete_elem_at_end(slist);
                insert_elem_at_begin(slist, num);
            }
        }
        print_all(slist);
    }
    return 0;
}